typedef char StackDataType;
typedef struct stack
{
    StackDataType* data;
    int size;
    int capacity;
}Stack;

//栈的初始化
void stackInit(Stack* pst)
{
    pst->data = NULL;
    pst->size = 0;
    pst->capacity = 0;
}

//栈的销毁
void stackDestroy(Stack* pst)
{
    free(pst->data);
    pst->size = 0;
    pst->capacity = 0;
}

//检查是否需要扩容
void checkCapacity(Stack* pst)
{
    if(pst->size == pst->capacity)
    {
        int newcapacity = pst->capacity == 0 ? 4 : (pst->capacity) * 2;
        StackDataType* temp = (StackDataType*)realloc(pst->data, sizeof(StackDataType) * newcapacity);
        if(temp == NULL)
        {
            perror("realloc fail");
            return;
        }
        pst->data = temp;
        pst->capacity = newcapacity;
    }
}

//栈是否为空
int stackIsEmpty(Stack* pst)
{
    return !(pst->size); 
}

//入栈
void stackPush(Stack* pst, StackDataType x)
{
    checkCapacity(pst);
    pst->data[pst->size++] = x;
}

//出栈
void stackPop(Stack* pst)
{
    if(!stackIsEmpty(pst))
    pst->size--;
}

//返回栈顶元素
StackDataType stackTop(Stack* pst)
{
    return pst->data[pst->size - 1];
}

//返回栈中元素个数
int stackSize(Stack* pst)
{
    return pst->size;
}

bool isValid(char* s ) {
    // write code here
    Stack st;
    stackInit(&st);
    int len = strlen(s);
    for(int i = 0; i < len; i++)
    {
        char ch = s[i];
        if(ch == '(' || ch == '[' || ch == '{')
        {
            stackPush(&st, ch);
        }
        else if(ch == ')' || ch == ']' || ch == '}')
        {
            if(stackIsEmpty(&st))
            return false;

            char temp = stackTop(&st);
            if(ch == ')' && temp == '(' || ch == ']' && temp == '[' || ch == '}' && temp == '{')
            stackPop(&st);
            else
            return false;
        }
    }

    return stackIsEmpty(&st);
}